//https://leetcode.cn/problems/maximum-earnings-from-taxi/description/?envType=daily-question&envId=2023-12-08


class Solution {
public:
    long long maxTaxiEarnings(int n, vector<vector<int>> &rides) {
        vector<vector<pair<int, int>>> groups(n + 1);
        for (auto &r : rides) {
            int start = r[0], end = r[1], tip = r[2];
            groups[end].push_back(make_pair(start, end - start + tip));
        }

        vector<long long> f(n + 1);
        for (int i = 2; i <= n; i++) {
            f[i] = f[i - 1];
            for (auto &[s, t] : groups[i]) {
                f[i] = max(f[i], f[s] + t);
            }
        }
        return f[n];
    }
};
